package Demo1;

//用栈求解括号对齐问题

import java.util.Scanner;
import java.util.Stack;

/**
 * 左括号必须用相同类型的右括号闭合。
 * 左括号必须以正确的顺序闭合。
 * 每个右括号都有一个对应的相同类型的左括号。
 */
class Solution2 {
    public boolean isValid(String x) {
        Stack<Character> stack = new Stack<>();
        stack.push(x.charAt(0));

        for (int i = 1; i < x.length(); i++) {
            if(stack.isEmpty()) {
                stack.push(x.charAt(i));
                continue;
            }
            if (stack.peek().equals('(')) {
                if(x.charAt(i) == ')') {
                    stack.pop();
                } else {
                    stack.push(x.charAt(i));
                }
            } else if (stack.peek().equals('[')) {
                if(x.charAt(i) == ']') {
                    stack.pop();
                } else {
                    stack.push(x.charAt(i));
                }
            } else if (stack.peek().equals('{')){
                if(x.charAt(i) == '}') {
                    stack.pop();
                } else {
                    stack.push(x.charAt(i));
                }
            } else {
                return false;
            }
        }

        if(stack.isEmpty()) {
            return true;
        }
        return false;
    }
}

public class t2 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        Solution2 s = new Solution2();
        System.out.println(s.isValid(scan.next()));
    }
}
